package newcoder_exp.justPractise;
import tree.*;
import java.util.*;
import org.junit.*;

public class NC5 {
    public class Solution {
        //所有节点都是一个数字，求出以根为最上元素到叶子的数字之和
        public int sumNumbers (TreeNode root) {
            dfs(root, new LinkedList<>());
            return sum;
        }

        int sum = 0;
        public void dfs(TreeNode root, LinkedList<Integer> cur) {
            // if (root == null) {
            //     return;
            // }
            if (root.left ==null && root.right == null) {
                int idx = 0;
                LinkedList<Integer> stack = new LinkedList<>(cur);
                stack.addLast(root.val);
                while (!stack.isEmpty()) {
                    sum += (int)Math.pow(10, idx++) * stack.pollLast();
                }
                return;
            }

            cur.offerLast(root.val);
            if (root.left != null)
                dfs(root.left, cur);
            if (root.right != null)
                dfs(root.right, cur);
            cur.pollLast();
        }


    }


    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{};
        TreeNode root = TreeUtils.deserialization("{1,2,9}");
        int res = s.sumNumbers(root);
        System.out.println(res);
    }
}
